package cn.yuemouren.map;


/**
 * @Author: Timi
 * @Description: 二分搜索树实现映射（map）
 * @Date: 2020/6/23 9:44
 */
public class BinarySearchMap<K extends Comparable<K>,V> implements Map<K,V>{

    private class Node{
        public K key;
        public V value;
        public Node left,right;

        public Node(K key){
            this(key,null);
        }

        public Node(K key,V value){
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    private Node root;
    private int size;

    public BinarySearchMap(Node root, int size) {
        this.root = null;
        this.size = 0;
    }

    /**
     * 添加映射关系
     * @param key
     * @param value
     */
    @Override
    public void add(K key, V value) {
        root = add(root,key,value);
    }

    private Node add(Node node,K key,V value){
        if(null == node){
            size++;
            return node = new Node(key,value);
        }
        if(key.compareTo(node.key) < 0){
            node.left = add(node.left, key, value);
        } else if(key.compareTo(node.key) > 0){
            node.right = add(node.right,key,value);
        } else{
            node.value = value;
        }
        return node;
    }

    private Node getNode(Node node,K key){
        if(null == node){
            return null;
        }
        if(key.compareTo(node.key) < 0){
            return getNode(node.left,key);
        } else if(key.compareTo(node.key) > 0){
            return getNode(node.left,key);
        } else{
            return node;
        }
    }

    /**
     * 更改键为key的value
     * @param key
     * @param newValue
     * @return
     */
    @Override
    public V set(K key, V newValue) {
        Node node = getNode(root, key);
        if(null == node){
            throw new IllegalArgumentException(key+" not is exist!");
        }
        V oldValue = node.value;
        node.value = newValue;
        return oldValue;
    }

    @Override
    public boolean contain(K key) {
        return getNode(root,key) != null;
    }

    @Override
    public V remove(K key) {
        return null;
    }

    private Node remove(Node node,K key){
        Node resNode = null;
        if(key.compareTo(node.key) < 0){
            resNode.left = remove(node.left,key);
        } else if(key.compareTo(node.key) > 0){
            resNode.right = remove(node.right,key);
        } else {//需要删除
            if(null == node.left){//没有左子树
                Node rightNode = node.right;
                node.right = null;
                size--;
                resNode = rightNode;
            } else if(null == node.right){//没有右子树
                Node leftNode = node.left;
                node.left = null;
                size--;
                resNode = leftNode;
            } else {//左右子树均存在,两种解决办法，一个是找左子树最大值，还有一个是找右子树最小值
                Node maxNode = getMax(node.left);
                Node removeNode = removeMax();
                maxNode.left = node.left;
                maxNode.right = node.right;
                resNode = node;
                node.left = node.right = null;
            }
        }
        return resNode;
    }

    public Node getMax(){
        if(null == root){
            return null;
        }
        return getMax(root);
    }

    /**
     * 递归实现获取树中最右节点（最大节点）
     * @param node
     * @return
     */
    private Node getMax(Node node) {
        if(null == node.right){
            return node;
        }
        return getMax(node.right);
    }

    public Node removeMax(){
        Node max = getMax(root);
        removeMax(root);
        return max;
    }

    /**
     * 递归实现删除树中最大值
     * @param node
     * @return
     */
    private Node removeMax(Node node) {
        if(null == node.right){
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return node;
    }

    @Override
    public int getSize() {
        return size;
    }
}
